Récursivité

On considère la fonction f suivante.

def f(n):
    if n == 0:
        return 0
    else:
        return 1 + f(n-1)

Pour calculer f(3), la machine virtuelle procède comme décrit à droite.

Pour cela, elle doit garder en mémoire tous les appels récursifs en cours, dans ce qu'on appelle la pile de récursion.

La taille de cette pile est limitée (à 1000 par défaut) ; il y a donc une limite à la profondeur des appels récursifs.

En pratique, l'appel f(10000) échoue avec l'erreur RecursionError: maximum recursion depth exceeded in comparison.

\hspace{1cm}

- elle rentre dans l'appel f(3)
- elle appelle f(2)
   - elle rentre dans l'appel f(2)
   - elle appelle f(1)
      - elle rentre dans l'appel f(1)
      - elle appelle f(0)
         - elle rentre dans l'appel f(0)
         - elle renvoie 0
      - l'appel f(1) renvoie 1 + 0 = 1
   - l'appel f(2) renvoie 1 + 1 = 2
- l'appel f(3) renvoie 1 + 2 = 3

La suite de Fibonacci $(F_n)_{n\in\N}$ est définie par $F_0 = 1$, $F_1 = 1$ et la relation de récurrence double $\forall n\in\N,\, F_{n+2} = F_{n+1} + F_n$.

On note $T_n$ le nombre total d'appels récursifs que réalise l'appel fib_rec(n). Cette suite vérifie $$T_0 = 0,\,T_1 = 0,\,T_2 = 2 \quad\et\quad \forall n\geq 2,\quad T_{n} = 2 + T_{n-1} + T_{n-2}.$$

La mémoïsation résout le problème de l'explosion des appels récursifs, en gardant en mémoire les valeurs qui ont déjà été calculées, dans une liste, ou un dictionnaire.

l = [1,1] # l[0] = F₀, l[1] = F₁
def mem_fibo_rec(n):
    if len(l)>n:
        return l[n]
    e = mem_fibo_rec(n-2) + mem_fibo_rec(n-1)
    # après l'appel fibo(n-1), la liste l contient
    # toutes les valeurs de la suite jusqu'a Fₙ₋₁
    assert(len(l) == n)
    l.append(e) # l[n] = Fₙ
    return e

# Version avec un dictionnaire
# Plus générale
d = {0: 1, 1: 1}
def mem_fibo_rec(n):
    if n in d:
        return d[n]
    e = mem_fibo_rec(n-2) + mem_fibo_rec(n-1)
    d[n] = e
    return e

La complexité de ces deux variantes est linéaire en $n$, comme la version itérative, mais elles utilisent une liste ou un dictionnaire de taille $n$, donc consomment plus de mémoire. On dit que leur complexité spatiale est linéaire.

Dans le calcul du pgcd de $a,b$ par l'algorithme d'Euclide, notons $a_n, b_n$ les entiers considérés à l'issue de la $n$-ième itération de la boucle, définis par $$\begin{cases}a_0 = a \\ b_0 = b \end{cases}\quad \et \quad \forall n\in\N,\,\begin{cases}a_{n+1} = b_n \\ b_{n+1} = r_n \end{cases}, \text{ où } a_n = b_n q_n + r_n \text{ est la division euclidienne.}$$

On se convainc aisément que pour tout $n\in\N$, $a_n$ et $b_n$ sont des combinaisons linéaires entières des entiers $a,b$ d'origine, c'est-à-dire qu'il existe $u_n,v_n\in\Z$ tels que $b_n = u_n a + v_n b$. En particulier, à la dernière étape, $\op{pgcd}(a,b)$ est lui-même une combinaison linéaire de $a,b$ :

On note $F_n$ le nombre d'opérations effectuées, dans le pire des cas, par un appel tri_fusion sur une liste de longueur $n$. On suppose que la suite $(F_n)_{n\in\N}$ est croissante³.

Lors de l'appel tri_fusion(n) on

1. découpe la liste en deux listes, de tailles $\lfloor \frac{n}{2}\rfloor$ et $\lceil \frac{n}{2} \rceil$
2. appelle tri_fusion sur les deux listes obtenues
3. fusionne les deux listes triées

Les étapes 1. et 3. ont une complexité linéaire. L'étape 2. réalise au plus $F_{\lfloor \frac{n}{2}\rfloor} + F_{\lceil \frac{n}{2} \rceil}$ opérations.

On en déduit qu'il existe $C\in\R_+$ tel que $$\forall n\geq 2,\, F_n \leq Cn + F_{\lfloor \frac{n}{2}\rfloor} + F_{\lceil \frac{n}{2} \rceil}.$$

Pour simplifier l'étude, on suppose dans un premier temps que $n = 2^p$. On a alors $\forall p,\,F_{2^p} \leq C 2^p + 2F_{2^{p-1}}$.

En réutilisant successivement cette même inégalité, on obtient

$$\begin{aligned}F_{2^p} & \leq C 2^p + 2F_{2^{p-1}} \leq C2^p + 2(C 2^{p-1} + 2 F_{2^{p-2}}) = C 2^p + C 2^p + 4 F_{p-2} \\ & \leq C 2^p + C 2^p + C 2^p + 2^3 F_{p-3} \\ & \leq \, \dots \\ & \leq p C 2^p + 2^p F_1 = C p 2^p\end{aligned}$$

Pour $n$ quelconque, on pose $p = \lfloor \log_2(n)\rfloor + 1$, de sorte que $n\lt 2^p$ et $2^p \leq 2n$. On a $$F_n \leq F_{2^p} \leq C p 2^p \leq 2C(\log_2 (n) + 1)n \leq C' n \ln n.$$

On s'intéresse à des algorithmes de tri dont la logique n'utilise que des comparaisons entre les éléments permettant de trier toutes les permutations de la liste l = [1, 2, …, n]. Pour toute permutation $\sigma$, on note $N_{\sigma}$ le nombre de comparaisons utilisées par l'algorithme pour trier cette permutation. On note $N = \max_{\sigma}(N_{\sigma})$ le nombre de comparaisons dans le pire des cas.

Malgré sa complexité temporelle en $O(n\ln n)$, la version implémentée dans l'exercice 2.4 est lente, à cause du grand nombre de copies de listes réalisées (chaque appel l[i:j] réalise une copie).

Bien que ces copies ne changent pas l'ordre de grandeur du nombre d'opérations total, elles changent l'ordre de grandeur de la quantité de mémoire utilisée. On pourrait justifier que la quantité de mémoire totale utilisée (on parle de complexité spatiale) est de l'ordre de $O(n\ln n)$, alors qu'un algorithme optimal n'en utilise que $O(n)$.

Ce défaut n'est pas intrinsèque au tri fusion, uniquement à cette implémentation en Python. Voici une autre implémentation du tri fusion qui n'alloue que $O(n)$ cases mémoires supplémentaires. Autre différence : au lieu de renvoyer une nouvelle liste triée, elle modifie la liste donnée en argument.

def fusion(l):
    # liste tampon
    t = [0] * len(l)
    # On définit une fonction auxiliaire, qui prend
    # en argument deux entiers a, b et qui va trier
    # la liste, entre les indices a (inclus) et b
    # (exclu)
    def fusion_aux(a, b):
        # Pour un seul élément, il n'y a rien à
        # faire
        if b - a <= 1:
            return
        c = (a + b) // 2
        # On trie les deux moitiés
        fusion_aux(a, c)
        fusion_aux(c, b)

        # On fusionne les deux moitiés dans le
        # tampon (de a à b)

        i, j = 0, 0
        while i < (c-a) and j < (b-c):
            if l[a+i] <= l[c+j]:
                t[a+i+j] = l[a+i]
                i += 1
            else:
                t[a+i+j] = l[c+j]
                j += 1
        if i == c-a:
            for k in range(j, b-c):
                t[a+i+k] = l[c+k]
        else:
            for k in range(i, c-a):
                t[a+k+j] = l[a+k]
        # On recopie la liste t dans l
        for k in range(a,b):
            l[k] = t[k]
    # Appel de la fonction auxiliaire
    fusion_aux(0, len(l))